package com.wfm.leetcode.editor.cn;

import java.util.Arrays;

/**
 * 除自身以外数组的乘积
 * 2025-02-25 23:40:27
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 */
class ProductOfArrayExceptSelf {

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 生成左边数组
        int[] left = new int[nums.length];
        left[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }
        // 生成右边数组
        int[] right = new int[nums.length];
        right[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        // 生成结果数组
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = left[i] * right[i];
        }
        return res;
    }

    // 可以优化空间，就是不生成R数组，用一个变量来跟踪，优化后，空间从O(n)优化到O(1)
//    public int[] productExceptSelf2(int[] nums) {
//        // 生成左边数组
//        int[] res = new int[nums.length];
//        res[0] = 1;
//        for (int i = 1; i < nums.length; i++) {
//            res[i] = res[i - 1] * nums[i - 1];
//        }
//        int right = 1;
//        // 生成结果数组
//        for (int i = nums.length-1; i >=0; i--) {
//            res[i]=res[i]*right;
//            right=right*nums[i];
//        }
//        return res;
//    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new ProductOfArrayExceptSelf().new Solution();
        System.out.println(Arrays.toString(solution.productExceptSelf(new int[]{1, 2, 3, 4})));
        System.out.println(Arrays.toString(solution.productExceptSelf(new int[]{-1, 1, 0, -3, 3})));
    }
}